package com.leetcode.editor.cn;

/**
 * @description: leetcode 第186号题目
 * @author:
 * @create: 2020-12-02 13:51
 **/

/**
 * 给定一个字符串，逐个翻转字符串中的每个单词。
 * <p>
 * 示例：
 * <p>
 * 输入: ['t','h','e',' ','s','k','y',' ','i','s',' ','b','l','u','e']
 * 输出: ['b','l','u','e',' ','i','s',' ','s','k','y',' ','t','h','e']
 * <p>
 * 注意：
 * <p>
 * 单词的定义是不包含空格的一系列字符
 * 输入字符串中不会包含前置或尾随的空格
 * 单词与单词之间永远是以单个空格隔开的
 * <p>
 * 进阶：使用 O(1) 额外空间复杂度的原地解法。
 */
public class P186ReverseWords {
    public static void main(String[] args) {
        Solution solution = new P186ReverseWords().new Solution();
        char[] words = {'t', 'h', 'e', ' ', 's', 'k', 'y', ' ', 'i', 's', ' ', 'b', 'l', 'u', 'e'};
        solution.reverseWords(words);
        System.out.println(String.valueOf(words));
    }

    class Solution {
        public void reverseWords(char[] s) {
            if (s == null || s.length == 0) {
                return;
            }
            int length = s.length;
            reverseArr(s, 0, length - 1);
            //双指针
            int pos = 0;
            int start = 0;
            while (pos < length) {
                if (s[pos] != ' ') {
                    pos++;
                } else {
                    reverseArr(s, start, pos - 1);
                    start = ++pos;
                }
            }
            if (start < length) {
                reverseArr(s, start, length - 1);
            }
        }

        //反转数组指定区间元素
        void reverseArr(char[] chars, int start, int end) {
            while (start < end) {
                char temp = chars[start];
                chars[start] = chars[end];
                chars[end] = temp;
                start++;
                end--;
            }
        }
    }
}
